#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

typedef char BTDataType;

typedef struct BinaryTreeNode 
{
	struct BinaryTreeNode* left;       // 记录左节点
	struct BinaryTreeNode* right;      // 记录右节点
	BTDataType data;                   // 存储数据
} BTNode;

//创建新节点
BTNode* CreateNode(BTDataType x) 
{
	BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
	if (new_node == NULL)
	{
		printf("malloc failed!\n");
		exit(-1);
	}
	new_node->data = x;
	new_node->left = new_node->right = NULL;

	return new_node;
}

//手动创建二叉树 
BTNode* CreateBinaryTree()
{
	BTNode* nodeA = CreateNode('A');
	BTNode* nodeB = CreateNode('B');
	BTNode* nodeC = CreateNode('C');
	BTNode* nodeD = CreateNode('D');
	BTNode* nodeE = CreateNode('E');
	BTNode* nodeF = CreateNode('F');

	nodeA->left = nodeB;         //           A
	nodeA->right = nodeC;        //       B        C
	nodeB->left = nodeD;         //    D        E    F
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

//二叉树前序遍历
void PreOrder(BTNode* root)
{
	//首先判断根是否为空，为空就返回
	if (root == NULL)
	{
		printf("NULL ");	// 暂时打印出来，便于观察	   
		return;
	}
	//走到这里说明不为空，根据前序遍历，先访问根节点
	printf("%c ", root->data);

	//然后遍历左子树（利用递归）
	PreOrder(root->left);

	//最后遍历右子树（利用递归）
	PreOrder(root->right);

	//           A
	//       B        C
	//    D        E    F        前序： 根 左 右
	//执行输出：  A B D NULL NULL NULL C E NULL NULL F NULL NULL
}

//二叉树中序遍历
void InOrder(BTNode* root) 
{
	if (root == NULL) 
	{
		printf("NULL ");  
		return;
	}

	InOrder(root->left);

	printf("%c ", root->data);

	InOrder(root->right);
	 //           A
     //       B        C
     //    D        E    F        中序：左 根 右
	 //执行输出：NULL D NULL B NULL A NULL E NULL C NULL F NULL
}

//二叉树后序遍历
void PostOrder(BTNode* root) 
{
	if (root == NULL) 
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);

	PostOrder(root->right);

	printf("%c ", root->data);
	//           A
	//       B        C
	//    D        E    F        后序：左  右  根
	//执行输出：NULL NULL D NULL B NULL NULL E NULL NULL F C A
}

int TreeSize(BTNode* root) 
{
	return root == NULL ? 0 
		: TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeLeafSize(BTNode* root) 
{
	if (root == NULL) 
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL) 
	{
		return 1;
	}

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeKLevelSize(BTNode* root, int  k) 
{
	assert(k > 0);
	if (root == NULL) 
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLevelSize(root->left, k - 1) 
		+  TreeKLevelSize(root->right, k - 1);
}

// 查找树里面值为x的那个节点
BTNode* TreeFind(BTNode* root, BTDataType x) 
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x) 
	{
		return root;
	}

	BTNode* lret = TreeFind(root->left, x);
	if (lret) 
	{
		return lret;
	}

	BTNode* rret = TreeFind(root->right, x);
	if (rret) 
	{
		return rret;
	}

	return NULL;
}

// 一般，如果选择一级指针，存在野指针问题，调用BinaryTreeDestory的人，把指针置空
// 这样保持接口的一致性
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);

	//printf("%p %c\n", root, root->data);
	free(root);
	root = NULL;
}

void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
	{       // 判断根是否为空
		return;
	}
	Queue pQ;
	QueueInit(&pQ);		// 初始化队列
	QueuePush(&pQ, root);	// 先让根进入队列
	while (!QueueEmpty(&pQ))
	{	// 只要队列内还有元素，就进入循环
		BTNode* front = QueueFront(&pQ);	// 记录当前对头数据
		printf("%c ", front->data);  // 打印队头数据
		QueuePop(&pQ);	 // 让队头出队

		if (front->left != NULL)
		{		// 如果队头元素的左子树不为空
			QueuePush(&pQ, front->left);	// 让左子树进入队列
		}
		if (front->right != NULL)
		{		// 如果对头元素的右子树不为空
			QueuePush(&pQ, front->right);	// 让右子树进入队列
		}
	}
	QueueDestroy(&pQ);// 销毁队列
}
bool BinaryTreeComplete(BTNode* root)
{
	Queue pQ;			// 建立队列
	QueueInit(&pQ);		// 初始化队列
	QueuePush(&pQ, root);	// 先让根进入队列
	while (!QueueEmpty(&pQ))
	{	// 只要队列内还有元素，就进入循环
		BTNode* front = QueueFront(&pQ);	// 记录当前队头数据
		QueuePop(&pQ);	 //队头出队

		if (front == NULL)
		{
			break;// 如果队头元素为空就跳出
		}
		else
		{
			QueuePush(&pQ, front->left);
			QueuePush(&pQ, front->right);
		}
	}
	//遇到空之后，检查队列剩下节点，
	while (!QueueEmpty(&pQ))
	{
		BTNode* front = QueueFront(&pQ);	// 记录当前队头数据
		QueuePop(&pQ);	 //队头出队
		if (front)//只要一个不为空就不是完全二叉树
		{
			QueueDestroy(&pQ);//注意return前销毁队列，否则会导致内存泄漏
			return false;
		}
	}
	QueueDestroy(&pQ);
	return true;//全为空就是完全二叉树
}

int main()
{
	BTNode* root = CreateBinaryTree();
	PreOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	printf("TreeSize:%d\n", TreeSize(root));

	printf("TreeLeafSize:%d\n", TreeLeafSize(root));

	printf("TreeKLevelSize:%d\n", TreeKLevelSize(root, 3));

	printf("TreeFind:%p\n", TreeFind(root, 'E'));
	printf("TreeFind:%p\n", TreeFind(root, 'F'));
	printf("TreeFind:%p\n", TreeFind(root, 'X'));//打印0 ：找不到

	BinaryTreeLevelOrder(root);
	printf("\n");

	printf("%d", BinaryTreeComplete(root));

	BinaryTreeDestory(root);
	root = NULL;
	return 0;
}

//965. 单值二叉树
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//
//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//    if (root->left && root->val != root->left->val)
//    {
//        return false;
//    }
//    if (root->right && root->val != root->right->val)
//    {
//        return false;
//    }
//    return isUnivalTree(root->left) && isUnivalTree(root->right);
//}

//104. 二叉树的最大深度
//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return 0;
//    }
//    int leftDepth = maxDepth(root->left);
//    int rightDepth = maxDepth(root->right);
//    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
//}

//226. 翻转二叉树
//难度简单
//给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
// 法一：
//struct TreeNode* invertTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return NULL;
//    }
//    struct TreeNode* tmp = root->left;
//    root->left = root->right;
//    root->right = tmp;
//
//    invertTree(root->left);
//    invertTree(root->right);
//    return root;
//}
//法二：
//struct TreeNode* invertTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return NULL;
//    }
//    struct TreeNode* rightTmp = root->right;
//    root->right = invertTree(root->left);
//    root->left = invertTree(rightTmp);
//
//    return root;
//}

//100. 相同的树
//给你两棵二叉树的根节点 root 和 root ，编写一个函数来检验这两棵树是否相同。
//如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//bool isSameTree(struct TreeNode* pi, struct TreeNode* q) {
//    if (pi == NULL && q == NULL)
//    {
//        return true;
//    }
//    if (pi == NULL || q == NULL)//其中一个为空，另一个不为空
//    {
//        return false;
//    }
//    if (pi->val != q->val)
//    {
//        return false;
//    }
//    return isSameTree(pi->left, q->left)
//        && isSameTree(pi->right, q->right);
//}

//572. 另一棵树的子树
//给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
//如果存在，返回 true ；否则，返回 false 。
//二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。
//tree 也可以看做它自身的一棵子树。
//bool isSameTree(struct TreeNode* pi, struct TreeNode* q)
//{
//    if (pi == NULL && q == NULL)
//    {
//        return true;
//    }
//    if (pi == NULL || q == NULL)//其中一个为空，另一个不为空
//    {
//        return false;
//    }
//    if (pi->val != q->val)
//    {
//        return false;
//    }
//    return isSameTree(pi->left, q->left)
//        && isSameTree(pi->right, q->right);
//}
//
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL)
//    {
//        return false;
//    }
//    if (isSameTree(root, subRoot))
//    {
//        return true;
//    }
//    //不一样就递归遍历这棵树
//    return isSubtree(root->left, subRoot)
//        || isSubtree(root->right, subRoot);
//    //只要有一个root返回true就行
//}

//二叉树遍历_牛客
//#include<stdio.h>
//#include<stdlib.h>
//
//typedef struct TreeNode
//{
//	struct TreeNode* left;
//	struct TreeNode* right;
//	char val;
//}TreeNode;
//
//TreeNode* CreateTree(char* str, int* pi)
//{
//	if (str[*pi] == '#')
//	{
//		(*pi)++;
//		return NULL;
//	}
//
//	//不是# 构造根
//	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
//	root->val = str[*pi];
//	(*pi)++;
//
//	root->left = CreateTree(str, pi);//递归构建左子树
//
//	root->right = CreateTree(str, pi);//递归构建右子树
//
//	return root;
//}
//
//void Inorder(TreeNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	Inorder(root->left);
//	printf("%c ", root->val);
//	Inorder(root->right);
//}
//
//int main()
//{
//	char str[100] = { 0 };
//	scanf("%s", str);
//
//	int i = 0;
//	TreeNode* root = CreateTree(str, &i);
//	Inorder(root);
//	printf("\n");
//	return 0;
//}

BTNode* CreateTree(char* str, int* pi)
{
	if (str[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	//不是# 构造根
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->data = str[*pi];
	(*pi)++;

	root->left = CreateTree(str, pi);//递归构建左子树

	root->right = CreateTree(str, pi);//递归构建右子树

	return root;
}